package hot_problems_100;

import java.util.HashSet;
import java.util.Set;

public class P3_0128 {
    /*
    *   给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
        请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
        0 <= nums.length <= 105
        -1e9 <= nums[i] <= 1e9
    * */
    public int longestConsecutive_slow(int[] nums) {
        Set<Integer> set = new HashSet<>(nums.length);
        for(int num: nums){
            set.add(num);
        }

        int left, right;
        int res = 0;
        Set<Integer> visited = new HashSet<>(nums.length);
        for(int i=0; i<nums.length; i++){
            if(visited.contains(nums[i])) continue;
            // 正向寻找
            right = nums[i] + 1;
            while(set.contains(right)) {
                visited.add(right);
                right ++ ;
            }
            left = nums[i] - 1;
            while(set.contains(left)) {
                visited.add(left);
                left --;
            }
            res = Math.max(right-left-1, res);
        }
        return res;
    }

    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>(nums.length);
        for(int num: nums){
            set.add(num);
        }

        int res = 0;
        int right = 0;
        // 需要注意的是，这里会有重复元素，所以使用set遍历更合适
        for(int num: set){
            if(!set.contains(num-1)){
                right = num + 1;
                while(set.contains(right)) right ++ ;
                res = Math.max(right - num, res);
            }
        }
        return res;
    }
}
